{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Forward Propagation, Backward Propagation, and Computational Graphs\n",
    "\n",
    "In the previous sections, we used mini-batch\n",
    "stochastic gradient descent to train our models.\n",
    "When we implemented the algorithm,\n",
    "we only worried about the calculations involved\n",
    "in *forward propagation* through the model.\n",
    "In other words, we implemented the calculations\n",
    "required for the model to generate output\n",
    "corresponding to some given input,\n",
    "but when it came time to calculate the gradients of each of our parameters,\n",
    "we invoked the `backward` function,\n",
    "relying on the `torch.autograd` module to figure out what to do.\n",
    "\n",
    "The automatic calculation of gradients profoundly simplifies\n",
    "the implementation of deep learning algorithms.\n",
    "Before automatic differentiation,\n",
    "even small changes to complicated models would require\n",
    "recalculating lots of derivatives by hand.\n",
    "Even academic papers would too often have to allocate\n",
    "lots of page real estate to deriving update rules.\n",
    "\n",
    "While we plan to continue relying on `torch.autograd`,\n",
    "and we have already come a long way\n",
    "without even discussing how these gradients\n",
    "are calculated efficiently under the hood,\n",
    "it's important that you know\n",
    "how updates are actually calculated\n",
    "if you want to go beyond a shallow understanding of deep learning.\n",
    "\n",
    "In this section, we'll peel back the curtain on some of the details\n",
    "of backward propagation (more commonly called *backpropagation* or *backprop*).\n",
    "To convey some insight for both the techniques and how they are implemented,\n",
    "we will rely on both mathematics and computational graphs\n",
    "to describe the mechanics behind neural network computations.\n",
    "To start, we will focus our exposition on\n",
    "a simple multilayer perceptron with a single hidden layer\n",
    "and $\\ell_2$ norm regularization.\n",
    "\n",
    "\n",
    "## Forward Propagation\n",
    "\n",
    "Forward propagation refers to the calculation and storage\n",
    "of intermediate variables (including outputs)\n",
    "for the neural network within the models\n",
    "in the order from input layer to output layer.\n",
    "In the following, we work in detail through the example of a deep network\n",
    "with one hidden layer step by step.\n",
    "This is a bit tedious but it will serve us well\n",
    "when discussing what really goes on when we call `backward`.\n",
    "\n",
    "For the sake of simplicity, let’s assume\n",
    "that the input example is $\\mathbf{x}\\in \\mathbb{R}^d$\n",
    "and there is no bias term.\n",
    "Here the intermediate variable is:\n",
    "\n",
    "$$\\mathbf{z}= \\mathbf{W}^{(1)} \\mathbf{x}$$\n",
    "\n",
    "$\\mathbf{W}^{(1)} \\in \\mathbb{R}^{h \\times d}$\n",
    "is the weight parameter of the hidden layer.\n",
    "After entering the intermediate variable $\\mathbf{z}\\in \\mathbb{R}^h$\n",
    "into the activation function $\\phi$ operated by the basic elements,\n",
    "we will obtain a hidden layer variable with the vector length of $h$,\n",
    "\n",
    "$$\\mathbf{h}= \\phi (\\mathbf{z}).$$\n",
    "\n",
    "The hidden variable $\\mathbf{h}$ is also an intermediate variable.\n",
    "Assuming the parameters of the output layer\n",
    "only possess a weight of $\\mathbf{W}^{(2)} \\in \\mathbb{R}^{q \\times h}$,\n",
    "we can obtain an output layer variable with a vector length of $q$:\n",
    "\n",
    "$$\\mathbf{o}= \\mathbf{W}^{(2)} \\mathbf{h}.$$\n",
    "\n",
    "Assuming the loss function is $l$ and the example label is $y$,\n",
    "we can then calculate the loss term for a single data example,\n",
    "\n",
    "$$L = l(\\mathbf{o}, y).$$\n",
    "\n",
    "According to the definition of $\\ell_2$ norm regularization,\n",
    "given the hyper-parameter $\\lambda$, the regularization term is\n",
    "\n",
    "$$s = \\frac{\\lambda}{2} \\left(\\|\\mathbf{W}^{(1)}\\|_F^2 + \\|\\mathbf{W}^{(2)}\\|_F^2\\right),$$\n",
    "\n",
    "where the Frobenius norm of the matrix is equivalent\n",
    "to the calculation of the $L_2$ norm\n",
    "after flattening the matrix to a vector.\n",
    "Finally, the model's regularized loss on a given data example is\n",
    "\n",
    "$$J = L + s.$$\n",
    "\n",
    "We refer to $J$ as the objective function of a given data example\n",
    "and refer to it as the ‘objective function’ in the following discussion.\n",
    "\n",
    "\n",
    "## Computational Graph of Forward Propagation\n",
    "\n",
    "Plotting computational graphs helps us visualize\n",
    "the dependencies of operators and variables within the calculation.\n",
    "The figure below contains the graph associated\n",
    "with the simple network described above.\n",
    "The lower-left corner signifies the input\n",
    "and the upper right corner the output.\n",
    "Notice that the direction of the arrows (which illustrate data flow)\n",
    "are primarily rightward and upward."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<svg height=\"100pt\" version=\"1.1\" viewBox=\"0 0 309 100\" width=\"309pt\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<defs>\n",
       "<g>\n",
       "<symbol id=\"glyph0-0\" overflow=\"visible\">\n",
       "<path d=\"\" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph0-1\" overflow=\"visible\">\n",
       "<path d=\"M 0.375 -3.9375 L 0.375 -3.703125 C 0.546875 -3.71875 0.609375 -3.71875 0.6875 -3.71875 C 0.96875 -3.71875 1.109375 -3.53125 1.203125 -3.09375 L 1.453125 -1.734375 L 1.0625 -1.09375 C 0.875 -0.78125 0.796875 -0.734375 0.640625 -0.734375 C 0.453125 -0.734375 0.34375 -0.921875 0.078125 -0.921875 C -0.203125 -0.921875 -0.40625 -0.703125 -0.40625 -0.40625 C -0.40625 -0.09375 -0.1875 0.109375 0.15625 0.109375 C 0.609375 0.109375 0.8125 -0.0625 1.34375 -0.921875 L 1.5625 -1.28125 C 1.75 -0.25 1.984375 0.109375 2.4375 0.109375 C 2.859375 0.109375 3.234375 -0.1875 3.78125 -0.984375 L 3.59375 -1.109375 C 3.25 -0.65625 3.15625 -0.578125 3 -0.578125 C 2.828125 -0.578125 2.734375 -0.703125 2.65625 -1.046875 L 2.375 -2.46875 C 2.65625 -2.984375 3 -3.3125 3.203125 -3.3125 C 3.40625 -3.3125 3.5 -3.125 3.71875 -3.125 C 3.984375 -3.125 4.21875 -3.34375 4.21875 -3.609375 C 4.21875 -3.890625 3.984375 -4.15625 3.703125 -4.15625 C 3.28125 -4.15625 2.984375 -3.9375 2.28125 -2.921875 C 2.140625 -3.6875 2.03125 -3.90625 1.859375 -4.15625 Z M 0.375 -3.9375 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph0-2\" overflow=\"visible\">\n",
       "<path d=\"M 8.453125 -6.015625 L 6.78125 -6.015625 L 6.78125 -5.796875 C 7.28125 -5.765625 7.34375 -5.71875 7.34375 -5.390625 C 7.34375 -5.28125 7.3125 -5.21875 7.203125 -4.984375 L 5.8125 -2.03125 L 5.515625 -4.65625 C 5.484375 -5 5.453125 -5.203125 5.453125 -5.3125 C 5.453125 -5.65625 5.53125 -5.75 6.015625 -5.796875 L 6.015625 -6.015625 L 3.609375 -6.015625 L 3.609375 -5.8125 C 4.15625 -5.734375 4.234375 -5.578125 4.234375 -4.859375 L 2.890625 -2.03125 L 2.53125 -5.171875 C 2.53125 -5.21875 2.53125 -5.296875 2.53125 -5.34375 C 2.53125 -5.625 2.65625 -5.734375 3.078125 -5.796875 L 3.078125 -6.015625 L 0.578125 -6.015625 L 0.578125 -5.8125 C 1.15625 -5.703125 1.1875 -5.625 1.28125 -4.984375 L 1.984375 0.15625 L 2.234375 0.15625 L 4.34375 -4.234375 L 4.875 0.15625 L 5.125 0.15625 L 7.671875 -5.0625 C 7.96875 -5.671875 8.078125 -5.75 8.453125 -5.8125 Z M 8.453125 -6.015625 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph0-3\" overflow=\"visible\">\n",
       "<path d=\"M 3.3125 -3.953125 L 3.3125 -4.046875 L 0.515625 -4.046875 L 0.109375 -2.65625 L 0.359375 -2.625 C 0.5 -3.046875 0.6875 -3.171875 1.015625 -3.171875 L 2.234375 -3.171875 L -0.390625 0.015625 L -0.15625 0.203125 C -0.09375 0.171875 -0.046875 0.125 0.015625 0.078125 C 0.140625 -0.015625 0.203125 -0.046875 0.296875 -0.046875 C 0.484375 -0.046875 0.640625 0.03125 0.96875 0.25 C 1.40625 0.5625 1.75 0.703125 2.125 0.703125 C 2.671875 0.703125 3.109375 0.4375 3.109375 -0.109375 C 3.109375 -0.375 2.890625 -0.59375 2.640625 -0.59375 C 2.390625 -0.59375 2.1875 -0.375 2.1875 -0.109375 C 2.1875 0.140625 2.359375 0.140625 2.359375 0.28125 C 2.359375 0.375 2.28125 0.4375 2.171875 0.4375 C 1.90625 0.4375 1.75 -0.046875 1.5625 -0.3125 C 1.328125 -0.625 1.140625 -0.78125 0.78125 -0.9375 Z M 3.3125 -3.953125 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph0-4\" overflow=\"visible\">\n",
       "<path d=\"M 4.28125 -1.28125 C 3.890625 -0.71875 3.71875 -0.53125 3.609375 -0.53125 C 3.53125 -0.53125 3.453125 -0.609375 3.453125 -0.671875 C 3.453125 -0.703125 3.453125 -0.71875 3.484375 -0.78125 L 4.015625 -2.421875 C 4.1875 -2.984375 4.28125 -3.3125 4.28125 -3.484375 C 4.28125 -3.90625 4.03125 -4.15625 3.59375 -4.15625 C 2.984375 -4.15625 2.5625 -3.8125 1.671875 -2.546875 L 2.640625 -6.296875 C 1.953125 -6.15625 1.5 -6.078125 0.765625 -6.015625 L 0.765625 -5.78125 L 0.96875 -5.78125 C 1.21875 -5.78125 1.34375 -5.6875 1.34375 -5.484375 C 1.34375 -5.40625 1.3125 -5.25 1.25 -5.0625 L -0.109375 0 L 0.96875 0 C 1.4375 -1.578125 1.609375 -2.015625 2.046875 -2.65625 C 2.4375 -3.234375 2.75 -3.515625 3 -3.515625 C 3.109375 -3.515625 3.171875 -3.46875 3.171875 -3.328125 C 3.171875 -3.265625 3.15625 -3.1875 3.109375 -3.046875 L 2.9375 -2.515625 C 2.484375 -1.1875 2.390625 -0.859375 2.390625 -0.5 C 2.390625 -0.140625 2.625 0.078125 2.984375 0.078125 C 3.53125 0.078125 3.890625 -0.21875 4.484375 -1.140625 Z M 4.28125 -1.28125 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph0-5\" overflow=\"visible\">\n",
       "<path d=\"M 2.515625 -4.15625 C 1.90625 -4.15625 1.328125 -3.921875 0.875 -3.46875 C 0.328125 -2.9375 -0.03125 -2.109375 -0.03125 -1.21875 C -0.03125 -0.328125 0.609375 0.109375 1.453125 0.109375 C 2.046875 0.109375 2.578125 -0.109375 3.03125 -0.5625 C 3.578125 -1.109375 3.96875 -1.953125 3.96875 -2.796875 C 3.96875 -3.625 3.421875 -4.15625 2.5625 -4.15625 Z M 2.890625 -3.34375 C 2.890625 -2.5625 2.5625 -1.3125 2.125 -0.578125 C 1.9375 -0.28125 1.71875 -0.140625 1.484375 -0.140625 C 1.21875 -0.140625 1.046875 -0.328125 1.046875 -0.71875 C 1.046875 -1.640625 1.390625 -3.015625 1.9375 -3.625 C 2.109375 -3.8125 2.28125 -3.890625 2.46875 -3.890625 C 2.734375 -3.890625 2.890625 -3.6875 2.890625 -3.34375 Z M 2.890625 -3.34375 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph1-0\" overflow=\"visible\">\n",
       "<path d=\"\" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph1-1\" overflow=\"visible\">\n",
       "<path d=\"M 1.828125 0.96875 C 0.984375 0.265625 0.796875 -0.40625 0.796875 -1.53125 C 0.796875 -2.6875 0.984375 -3.25 1.828125 -3.953125 L 1.765625 -4.0625 C 0.8125 -3.484375 0.28125 -2.625 0.28125 -1.515625 C 0.28125 -0.484375 0.796875 0.515625 1.75 1.0625 Z M 1.828125 0.96875 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph1-2\" overflow=\"visible\">\n",
       "<path d=\"M 2.359375 0 L 2.359375 -0.09375 C 1.90625 -0.09375 1.796875 -0.203125 1.796875 -0.453125 L 1.796875 -4.03125 L 1.734375 -4.0625 L 0.671875 -3.515625 L 0.671875 -3.421875 L 0.828125 -3.484375 C 0.9375 -3.53125 1.03125 -3.5625 1.09375 -3.5625 C 1.21875 -3.5625 1.28125 -3.46875 1.28125 -3.265625 L 1.28125 -0.5625 C 1.28125 -0.234375 1.15625 -0.109375 0.703125 -0.09375 L 0.703125 0 Z M 2.359375 0 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph1-3\" overflow=\"visible\">\n",
       "<path d=\"M 0.171875 -3.953125 C 1.046875 -3.28125 1.1875 -2.59375 1.1875 -1.46875 C 1.1875 -0.296875 1.03125 0.265625 0.171875 0.96875 L 0.234375 1.0625 C 1.1875 0.484375 1.703125 -0.375 1.703125 -1.484375 C 1.703125 -2.5 1.15625 -3.5 0.25 -4.0625 Z M 0.171875 -3.953125 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph1-4\" overflow=\"visible\">\n",
       "<path d=\"M 2.84375 -0.828125 L 2.765625 -0.859375 C 2.5625 -0.515625 2.4375 -0.453125 2.1875 -0.453125 L 0.78125 -0.453125 L 1.765625 -1.515625 C 2.296875 -2.078125 2.53125 -2.53125 2.53125 -3 C 2.53125 -3.59375 2.109375 -4.0625 1.421875 -4.0625 C 0.6875 -4.0625 0.3125 -3.5625 0.1875 -2.859375 L 0.3125 -2.828125 C 0.546875 -3.421875 0.75 -3.609375 1.1875 -3.609375 C 1.703125 -3.609375 2.015625 -3.3125 2.015625 -2.765625 C 2.015625 -2.25 1.8125 -1.796875 1.234375 -1.203125 L 0.171875 -0.078125 L 0.171875 0 L 2.515625 0 Z M 2.84375 -0.828125 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph2-0\" overflow=\"visible\">\n",
       "<path d=\"M 0.296875 0 L 0.296875 -6 L 2.703125 -6 L 2.703125 0 Z M 2.40625 -0.296875 L 2.40625 -5.703125 L 0.59375 -5.703125 L 0.59375 -0.296875 Z M 2.40625 -0.296875 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph2-1\" overflow=\"visible\">\n",
       "<path d=\"M 1.203125 0 L 0.5625 0 L 2.65625 -2.4375 L 0.5625 -4.84375 L 1.25 -4.84375 L 3 -3.015625 L 4.8125 -4.84375 L 5.4375 -4.84375 L 3.3125 -2.4375 L 5.4375 0 L 4.75 0 L 3 -1.953125 Z M 1.203125 0 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph3-0\" overflow=\"visible\">\n",
       "<path d=\"\" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph3-1\" overflow=\"visible\">\n",
       "<path d=\"M 4.328125 -6.140625 L 3.640625 -6.140625 L 3.03125 -3.96875 L 2.890625 -3.96875 C 1.25 -3.96875 0.25 -2.0625 0.25 -1.15625 C 0.25 -0.578125 0.46875 -0.15625 0.9375 0 C 1.15625 0.078125 1.515625 0.09375 1.90625 0.09375 L 1.40625 1.84375 L 2.109375 1.84375 L 2.59375 0.09375 C 4.375 0.09375 5.359375 -1.6875 5.359375 -2.734375 C 5.359375 -3.359375 5.078125 -3.6875 4.640625 -3.859375 C 4.390625 -3.953125 4.140625 -3.96875 3.71875 -3.96875 Z M 3.671875 -3.78125 C 3.859375 -3.78125 4.109375 -3.765625 4.1875 -3.71875 C 4.421875 -3.578125 4.59375 -3.34375 4.59375 -2.9375 C 4.59375 -2.203125 4.015625 -0.609375 3.28125 -0.234375 C 3.03125 -0.109375 2.875 -0.09375 2.65625 -0.09375 Z M 1.953125 -0.09375 C 1.75 -0.09375 1.578125 -0.109375 1.4375 -0.15625 C 1.15625 -0.265625 1 -0.53125 1 -0.90625 C 1 -2.171875 1.9375 -3.78125 2.984375 -3.78125 Z M 1.953125 -0.09375 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph4-0\" overflow=\"visible\">\n",
       "<path d=\"\" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph4-1\" overflow=\"visible\">\n",
       "<path d=\"M 2.1875 -1.671875 C 2.03125 -2.46875 1.5625 -3.96875 1.421875 -3.96875 L 1.390625 -3.96875 C 0.90625 -3.890625 0.609375 -3.84375 0.421875 -3.8125 C 0.328125 -3.78125 0.234375 -3.765625 0.140625 -3.75 L 0.140625 -3.59375 C 0.234375 -3.625 0.3125 -3.640625 0.40625 -3.640625 C 0.78125 -3.640625 0.9375 -3.5 1.109375 -3.0625 C 1.34375 -2.453125 1.84375 -0.4375 1.84375 -0.078125 C 1.84375 0.03125 1.8125 0.140625 1.75 0.25 C 1.6875 0.359375 1.28125 0.890625 1.109375 1.0625 C 0.90625 1.28125 0.796875 1.359375 0.6875 1.359375 C 0.453125 1.359375 0.453125 1.109375 0.140625 1.109375 C -0.0625 1.109375 -0.21875 1.265625 -0.21875 1.46875 C -0.21875 1.703125 -0.03125 1.859375 0.25 1.859375 C 0.75 1.859375 1.71875 0.8125 2.65625 -0.734375 C 3.40625 -1.96875 3.828125 -2.96875 3.828125 -3.46875 C 3.828125 -3.75 3.640625 -3.96875 3.359375 -3.96875 C 3.15625 -3.96875 3 -3.828125 3 -3.640625 C 3 -3.484375 3.0625 -3.40625 3.234375 -3.28125 C 3.40625 -3.171875 3.46875 -3.125 3.46875 -3 C 3.46875 -2.59375 3.140625 -1.953125 2.375 -0.6875 Z M 2.1875 -1.671875 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph4-2\" overflow=\"visible\">\n",
       "<path d=\"M 5.03125 -1.625 L 4.84375 -1.671875 C 4.59375 -1.15625 4.40625 -0.859375 4.109375 -0.671875 C 3.671875 -0.375 3.390625 -0.328125 2.5 -0.328125 C 1.75 -0.328125 1.546875 -0.40625 1.546875 -0.6875 C 1.546875 -0.8125 1.578125 -0.96875 1.640625 -1.171875 L 2.71875 -5.046875 C 2.859375 -5.546875 3.09375 -5.703125 3.625 -5.734375 L 3.625 -5.875 L 1.171875 -5.875 L 1.171875 -5.734375 C 1.734375 -5.703125 1.859375 -5.609375 1.859375 -5.34375 C 1.859375 -5.21875 1.84375 -5.03125 1.765625 -4.78125 L 0.671875 -0.84375 C 0.5 -0.28125 0.4375 -0.203125 -0.078125 -0.140625 L -0.078125 0 L 4.515625 0 Z M 5.03125 -1.625 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph4-3\" overflow=\"visible\">\n",
       "<path d=\"M 3.296875 -3.984375 L 3.171875 -3.984375 C 3.09375 -3.859375 3.03125 -3.8125 2.890625 -3.8125 C 2.828125 -3.8125 2.75 -3.828125 2.578125 -3.875 C 2.34375 -3.9375 2.21875 -3.96875 2.0625 -3.96875 C 1.40625 -3.96875 0.984375 -3.59375 0.984375 -3 C 0.984375 -2.703125 1.15625 -2.296875 1.546875 -1.8125 C 1.90625 -1.375 2.046875 -1.078125 2.046875 -0.78125 C 2.046875 -0.34375 1.796875 -0.09375 1.375 -0.09375 C 0.90625 -0.09375 0.59375 -0.453125 0.46875 -1.3125 L 0.328125 -1.3125 L 0.140625 0.109375 L 0.28125 0.109375 C 0.34375 -0.03125 0.453125 -0.078125 0.546875 -0.078125 C 0.640625 -0.078125 0.78125 -0.0625 0.9375 0.015625 C 1.15625 0.09375 1.28125 0.09375 1.4375 0.09375 C 2.1875 0.09375 2.734375 -0.359375 2.734375 -1.109375 C 2.734375 -1.453125 2.578125 -1.8125 2.125 -2.328125 C 1.765625 -2.75 1.640625 -3 1.640625 -3.25 C 1.640625 -3.578125 1.859375 -3.765625 2.171875 -3.765625 C 2.609375 -3.765625 2.875 -3.46875 2.96875 -2.71875 L 3.109375 -2.71875 Z M 3.296875 -3.984375 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph4-4\" overflow=\"visible\">\n",
       "<path d=\"M 4.421875 -5.875 L 2.140625 -5.875 L 2.140625 -5.734375 C 2.703125 -5.671875 2.828125 -5.609375 2.828125 -5.359375 C 2.828125 -5.234375 2.796875 -5.046875 2.71875 -4.78125 L 1.578125 -0.703125 C 1.46875 -0.34375 1.3125 -0.125 1.09375 -0.125 C 0.875 -0.125 0.78125 -0.21875 0.78125 -0.484375 C 0.78125 -0.5625 0.8125 -0.609375 0.8125 -0.71875 C 0.8125 -0.9375 0.59375 -1.140625 0.34375 -1.140625 C 0.109375 -1.140625 -0.046875 -0.921875 -0.046875 -0.625 C -0.046875 -0.15625 0.375 0.15625 1 0.15625 C 1.453125 0.15625 1.859375 0.015625 2.109375 -0.328125 C 2.34375 -0.640625 2.5625 -1.078125 2.75 -1.765625 L 3.6875 -5.0625 C 3.828125 -5.609375 3.90625 -5.65625 4.421875 -5.734375 Z M 4.421875 -5.875 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph4-5\" overflow=\"visible\">\n",
       "<path d=\"M 5.3125 -1.984375 L 5.3125 -2.578125 L 3.34375 -2.578125 L 3.34375 -4.546875 L 2.75 -4.546875 L 2.75 -2.578125 L 0.78125 -2.578125 L 0.78125 -1.984375 L 2.75 -1.984375 L 2.75 0 L 3.34375 0 L 3.34375 -1.984375 Z M 5.3125 -1.984375 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph5-0\" overflow=\"visible\">\n",
       "<path d=\"\" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph5-1\" overflow=\"visible\">\n",
       "<path d=\"M 0.6875 -3.5 C 0.9375 -3.328125 1.21875 -3.25 1.484375 -3.234375 C 1.359375 -3.046875 1.234375 -2.84375 1.125 -2.640625 C 0.703125 -1.90625 0.4375 -1.171875 0.4375 -0.6875 C 0.4375 -0.15625 0.796875 0.09375 1.21875 0.09375 C 1.78125 0.09375 2.3125 -0.40625 3.265625 -1.515625 L 3.0625 -1.671875 C 2.203125 -0.671875 1.703125 -0.171875 1.28125 -0.171875 C 1.03125 -0.171875 0.953125 -0.34375 0.953125 -0.5625 C 0.953125 -1.15625 1.765625 -2.484375 2.234375 -3.234375 C 3.828125 -3.46875 5.140625 -4.640625 5.140625 -5.578125 C 5.140625 -6 4.9375 -6.1875 4.5625 -6.1875 C 3.828125 -6.1875 2.609375 -4.90625 1.671875 -3.515625 C 1.390625 -3.515625 1.109375 -3.53125 0.8125 -3.734375 Z M 2.40625 -3.5625 C 2.875 -4.296875 3.375 -5.015625 3.8125 -5.46875 C 4.046875 -5.703125 4.296875 -5.890625 4.546875 -5.890625 C 4.765625 -5.890625 4.875 -5.78125 4.875 -5.609375 C 4.875 -4.75 3.828125 -3.875 2.421875 -3.5625 Z M 2.40625 -3.5625 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph6-0\" overflow=\"visible\">\n",
       "<path d=\"\" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph6-1\" overflow=\"visible\">\n",
       "<path d=\"M 0.703125 -3.546875 C 0.953125 -4.015625 1.3125 -4.21875 1.734375 -4.21875 C 2.28125 -4.21875 2.5625 -3.859375 2.5625 -3.375 C 2.5625 -3.21875 2.546875 -3.09375 2.5 -3 C 2.328125 -2.625 2.015625 -2.171875 1.546875 -1.6875 L 0.078125 -0.125 L 0.078125 0 L 2.5625 0 L 2.90625 -0.9375 L 2.796875 -0.984375 C 2.625 -0.640625 2.484375 -0.53125 2.078125 -0.53125 L 0.8125 -0.53125 L 0.8125 -0.5625 L 2.125 -1.90625 C 2.953125 -2.765625 3.15625 -3.078125 3.15625 -3.546875 C 3.15625 -4.21875 2.703125 -4.734375 2.03125 -4.734375 C 1.703125 -4.734375 1.40625 -4.640625 1.140625 -4.4375 C 0.890625 -4.25 0.734375 -4.015625 0.5625 -3.59375 Z M 0.703125 -3.546875 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "</g>\n",
       "</defs>\n",
       "<g id=\"surface1\">\n",
       "<rect height=\"100\" style=\"fill:rgb(100%,100%,100%);fill-opacity:1;stroke:none;\" width=\"309\" x=\"0\" y=\"0\"/>\n",
       "<rect height=\"100\" style=\"fill:rgb(100%,100%,100%);fill-opacity:1;stroke:none;\" width=\"309\" x=\"0\" y=\"0\"/>\n",
       "<path d=\"M 287.398438 447.199219 L 308.398438 447.199219 L 308.398438 468.199219 L 287.398438 468.199219 Z M 287.398438 447.199219 \" style=\"fill-rule:nonzero;fill:rgb(100%,100%,100%);fill-opacity:1;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-286,-369)\"/>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"9.65\" xlink:href=\"#glyph0-1\" y=\"91.20001\"/>\n",
       "</g>\n",
       "<path d=\"M 328.226562 408.398438 L 349.226562 408.398438 L 349.226562 429.398438 L 328.226562 429.398438 Z M 328.226562 408.398438 \" style=\"fill-rule:nonzero;fill:rgb(39.99939%,74.900818%,100%);fill-opacity:1;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-286,-369)\"/>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"45.2265\" xlink:href=\"#glyph0-2\" y=\"52.90001\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"53.2275\" xlink:href=\"#glyph1-1\" y=\"48.90001\"/>\n",
       "  <use x=\"55.2255\" xlink:href=\"#glyph1-2\" y=\"48.90001\"/>\n",
       "  <use x=\"58.2255\" xlink:href=\"#glyph1-3\" y=\"48.90001\"/>\n",
       "</g>\n",
       "<path d=\"M 60.148438 81.273438 C 64.25 85.375 64.25 92.023438 60.148438 96.125 C 56.050781 100.226562 49.402344 100.226562 45.300781 96.125 C 41.199219 92.023438 41.199219 85.375 45.300781 81.273438 C 49.402344 77.175781 56.050781 77.175781 60.148438 81.273438 \" style=\" stroke:none;fill-rule:nonzero;fill:rgb(69.802856%,85.096741%,100%);fill-opacity:1;\"/>\n",
       "<path d=\"M 346.148438 450.277344 C 350.25 454.375 350.25 461.023438 346.148438 465.125 C 342.050781 469.226562 335.402344 469.226562 331.300781 465.125 C 327.199219 461.023438 327.199219 454.375 331.300781 450.277344 C 335.402344 446.175781 342.050781 446.175781 346.148438 450.277344 \" style=\"fill:none;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-286,-369)\"/>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"49.72793\" xlink:href=\"#glyph2-1\" y=\"90.324278\"/>\n",
       "</g>\n",
       "<path d=\"M 369.050781 447.199219 L 390.050781 447.199219 L 390.050781 468.199219 L 369.050781 468.199219 Z M 369.050781 447.199219 \" style=\"fill-rule:nonzero;fill:rgb(100%,100%,100%);fill-opacity:1;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-286,-369)\"/>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"91.79951\" xlink:href=\"#glyph0-3\" y=\"91.20001\"/>\n",
       "</g>\n",
       "<path d=\"M 141.800781 81.273438 C 145.898438 85.375 145.898438 92.023438 141.800781 96.125 C 137.699219 100.226562 131.050781 100.226562 126.949219 96.125 C 122.851562 92.023438 122.851562 85.375 126.949219 81.273438 C 131.050781 77.175781 137.699219 77.175781 141.800781 81.273438 \" style=\" stroke:none;fill-rule:nonzero;fill:rgb(69.802856%,85.096741%,100%);fill-opacity:1;\"/>\n",
       "<path d=\"M 427.800781 450.277344 C 431.898438 454.375 431.898438 461.023438 427.800781 465.125 C 423.699219 469.226562 417.050781 469.226562 412.949219 465.125 C 408.851562 461.023438 408.851562 454.375 412.949219 450.277344 C 417.050781 446.175781 423.699219 446.175781 427.800781 450.277344 \" style=\"fill:none;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-286,-369)\"/>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"131.5535\" xlink:href=\"#glyph3-1\" y=\"91.20001\"/>\n",
       "</g>\n",
       "<path d=\"M 450.699219 447.199219 L 471.699219 447.199219 L 471.699219 468.199219 L 450.699219 468.199219 Z M 450.699219 447.199219 \" style=\"fill-rule:nonzero;fill:rgb(100%,100%,100%);fill-opacity:1;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-286,-369)\"/>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"172.698\" xlink:href=\"#glyph0-4\" y=\"91.20001\"/>\n",
       "</g>\n",
       "<path d=\"M 532.351562 447.199219 L 553.351562 447.199219 L 553.351562 468.199219 L 532.351562 468.199219 Z M 532.351562 447.199219 \" style=\"fill-rule:nonzero;fill:rgb(100%,100%,100%);fill-opacity:1;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-286,-369)\"/>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"254.6\" xlink:href=\"#glyph0-5\" y=\"91.20001\"/>\n",
       "</g>\n",
       "<path d=\"M 491.199219 408.398438 L 512.199219 408.398438 L 512.199219 429.398438 L 491.199219 429.398438 Z M 491.199219 408.398438 \" style=\"fill-rule:nonzero;fill:rgb(39.99939%,74.900818%,100%);fill-opacity:1;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-286,-369)\"/>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"208.2001\" xlink:href=\"#glyph0-2\" y=\"52.90001\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"216.2011\" xlink:href=\"#glyph1-1\" y=\"48.90001\"/>\n",
       "  <use x=\"218.1991\" xlink:href=\"#glyph1-4\" y=\"48.90001\"/>\n",
       "  <use x=\"221.1991\" xlink:href=\"#glyph1-3\" y=\"48.90001\"/>\n",
       "</g>\n",
       "<path d=\"M 223.449219 81.273438 C 227.550781 85.375 227.550781 92.023438 223.449219 96.125 C 219.347656 100.226562 212.699219 100.226562 208.601562 96.125 C 204.5 92.023438 204.5 85.375 208.601562 81.273438 C 212.699219 77.175781 219.347656 77.175781 223.449219 81.273438 \" style=\" stroke:none;fill-rule:nonzero;fill:rgb(69.802856%,85.096741%,100%);fill-opacity:1;\"/>\n",
       "<path d=\"M 509.449219 450.277344 C 513.550781 454.375 513.550781 461.023438 509.449219 465.125 C 505.347656 469.226562 498.699219 469.226562 494.601562 465.125 C 490.5 461.023438 490.5 454.375 494.601562 450.277344 C 498.699219 446.175781 505.347656 446.175781 509.449219 450.277344 \" style=\"fill:none;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-286,-369)\"/>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"213.02793\" xlink:href=\"#glyph2-1\" y=\"90.324278\"/>\n",
       "</g>\n",
       "<path d=\"M 573.175781 408.398438 L 594.175781 408.398438 L 594.175781 429.398438 L 573.175781 429.398438 Z M 573.175781 408.398438 \" style=\"fill-rule:nonzero;fill:rgb(100%,100%,100%);fill-opacity:1;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-286,-369)\"/>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"295.677\" xlink:href=\"#glyph4-1\" y=\"52.40001\"/>\n",
       "</g>\n",
       "<path d=\"M 305.097656 81.273438 C 309.199219 85.375 309.199219 92.023438 305.097656 96.125 C 301 100.226562 294.351562 100.226562 290.25 96.125 C 286.148438 92.023438 286.148438 85.375 290.25 81.273438 C 294.351562 77.175781 301 77.175781 305.097656 81.273438 \" style=\" stroke:none;fill-rule:nonzero;fill:rgb(69.802856%,85.096741%,100%);fill-opacity:1;\"/>\n",
       "<path d=\"M 591.097656 450.277344 C 595.199219 454.375 595.199219 461.023438 591.097656 465.125 C 587 469.226562 580.351562 469.226562 576.25 465.125 C 572.148438 461.023438 572.148438 454.375 576.25 450.277344 C 580.351562 446.175781 587 446.175781 591.097656 450.277344 \" style=\"fill:none;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-286,-369)\"/>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"295.0695\" xlink:href=\"#glyph5-1\" y=\"91.20001\"/>\n",
       "</g>\n",
       "<path d=\"M 532.351562 408.398438 L 553.351562 408.398438 L 553.351562 429.398438 L 532.351562 429.398438 Z M 532.351562 408.398438 \" style=\"fill-rule:nonzero;fill:rgb(100%,100%,100%);fill-opacity:1;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-286,-369)\"/>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"254.348\" xlink:href=\"#glyph4-2\" y=\"52.40001\"/>\n",
       "</g>\n",
       "<path d=\"M 308.398438 457.699219 L 322.324219 457.699219 \" style=\"fill:none;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-286,-369)\"/>\n",
       "<path d=\"M 326.324219 457.699219 L 322.324219 457.699219 M 322.324219 456.199219 L 326.324219 457.699219 L 322.324219 459.199219 \" style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-286,-369)\"/>\n",
       "<path d=\"M 338.726562 429.398438 L 338.726562 441.300781 \" style=\"fill:none;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-286,-369)\"/>\n",
       "<path d=\"M 338.726562 445.300781 L 338.726562 441.300781 M 340.226562 441.300781 L 338.726562 445.300781 L 337.226562 441.300781 \" style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-286,-369)\"/>\n",
       "<path d=\"M 349.226562 457.699219 L 363.148438 457.699219 \" style=\"fill:none;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-286,-369)\"/>\n",
       "<path d=\"M 367.148438 457.699219 L 363.148438 457.699219 M 363.148438 456.199219 L 367.148438 457.699219 L 363.148438 459.199219 \" style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-286,-369)\"/>\n",
       "<path d=\"M 390.050781 457.699219 L 403.976562 457.699219 \" style=\"fill:none;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-286,-369)\"/>\n",
       "<path d=\"M 407.976562 457.699219 L 403.976562 457.699219 M 403.976562 456.199219 L 407.976562 457.699219 L 403.976562 459.199219 \" style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-286,-369)\"/>\n",
       "<path d=\"M 430.875 457.699219 L 444.800781 457.699219 \" style=\"fill:none;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-286,-369)\"/>\n",
       "<path d=\"M 448.800781 457.699219 L 444.800781 457.699219 M 444.800781 456.199219 L 448.800781 457.699219 L 444.800781 459.199219 \" style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-286,-369)\"/>\n",
       "<path d=\"M 501.785156 429.398438 L 501.886719 441.300781 \" style=\"fill:none;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-286,-369)\"/>\n",
       "<path d=\"M 501.921875 445.300781 L 501.886719 441.300781 M 503.386719 441.289062 L 501.921875 445.300781 L 500.386719 441.3125 \" style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-286,-369)\"/>\n",
       "<path d=\"M 471.699219 457.699219 L 485.625 457.699219 \" style=\"fill:none;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-286,-369)\"/>\n",
       "<path d=\"M 489.625 457.699219 L 485.625 457.699219 M 485.625 456.199219 L 489.625 457.699219 L 485.625 459.199219 \" style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-286,-369)\"/>\n",
       "<path d=\"M 512.523438 457.699219 L 526.449219 457.699219 \" style=\"fill:none;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-286,-369)\"/>\n",
       "<path d=\"M 530.449219 457.699219 L 526.449219 457.699219 M 526.449219 456.199219 L 530.449219 457.699219 L 526.449219 459.199219 \" style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-286,-369)\"/>\n",
       "<path d=\"M 553.351562 457.699219 L 567.273438 457.699219 \" style=\"fill:none;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-286,-369)\"/>\n",
       "<path d=\"M 571.273438 457.699219 L 567.273438 457.699219 M 567.273438 456.199219 L 571.273438 457.699219 L 567.273438 459.199219 \" style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-286,-369)\"/>\n",
       "<path d=\"M 583.675781 429.398438 L 583.675781 441.300781 \" style=\"fill:none;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-286,-369)\"/>\n",
       "<path d=\"M 583.675781 445.300781 L 583.675781 441.300781 M 585.175781 441.300781 L 583.675781 445.300781 L 582.175781 441.300781 \" style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-286,-369)\"/>\n",
       "<path d=\"M 576.0625 450.464844 L 557.625 432.945312 \" style=\"fill:none;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-286,-369)\"/>\n",
       "<path d=\"M 554.726562 430.1875 L 557.625 432.945312 M 556.59375 434.03125 L 554.726562 430.1875 L 558.660156 431.855469 \" style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-286,-369)\"/>\n",
       "<path d=\"M 427.800781 411.476562 C 431.902344 415.574219 431.902344 422.222656 427.800781 426.324219 C 423.699219 430.425781 417.050781 430.425781 412.949219 426.324219 C 408.851562 422.222656 408.851562 415.574219 412.949219 411.476562 C 417.050781 407.375 423.699219 407.375 427.800781 411.476562 \" style=\"fill-rule:nonzero;fill:rgb(69.802856%,85.096741%,100%);fill-opacity:1;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-286,-369)\"/>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"130.1234\" xlink:href=\"#glyph4-2\" y=\"50.90001\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"135.1274\" xlink:href=\"#glyph6-1\" y=\"54.90001\"/>\n",
       "</g>\n",
       "<path d=\"M 349.226562 418.898438 L 403.976562 418.898438 \" style=\"fill:none;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-286,-369)\"/>\n",
       "<path d=\"M 407.976562 418.898438 L 403.976562 418.898438 M 403.976562 417.398438 L 407.976562 418.898438 L 403.976562 420.398438 \" style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-286,-369)\"/>\n",
       "<path d=\"M 491.199219 418.898438 L 436.777344 418.898438 \" style=\"fill:none;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-286,-369)\"/>\n",
       "<path d=\"M 432.777344 418.898438 L 436.777344 418.898438 M 436.777344 420.398438 L 432.777344 418.898438 L 436.777344 417.398438 \" style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-286,-369)\"/>\n",
       "<path d=\"M 409.875 369.601562 L 430.875 369.601562 L 430.875 390.601562 L 409.875 390.601562 Z M 409.875 369.601562 \" style=\"fill-rule:nonzero;fill:rgb(100%,100%,100%);fill-opacity:1;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-286,-369)\"/>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"132.6249\" xlink:href=\"#glyph4-3\" y=\"13.60001\"/>\n",
       "</g>\n",
       "<path d=\"M 573.175781 369.601562 L 594.175781 369.601562 L 594.175781 390.601562 L 573.175781 390.601562 Z M 573.175781 369.601562 \" style=\"fill-rule:nonzero;fill:rgb(100%,100%,100%);fill-opacity:1;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-286,-369)\"/>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"295.677\" xlink:href=\"#glyph4-4\" y=\"13.60001\"/>\n",
       "</g>\n",
       "<path d=\"M 509.125 372.675781 C 513.222656 376.777344 513.222656 383.425781 509.125 387.523438 C 505.023438 391.625 498.375 391.625 494.273438 387.523438 C 490.171875 383.425781 490.171875 376.777344 494.273438 372.675781 C 498.375 368.574219 505.023438 368.574219 509.125 372.675781 \" style=\"fill-rule:nonzero;fill:rgb(69.802856%,85.096741%,100%);fill-opacity:1;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-286,-369)\"/>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"212.6611\" xlink:href=\"#glyph4-5\" y=\"13.60001\"/>\n",
       "</g>\n",
       "<path d=\"M 420.601562 407.800781 L 420.507812 396.5 \" style=\"fill:none;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-286,-369)\"/>\n",
       "<path d=\"M 420.476562 392.5 L 420.507812 396.5 M 419.007812 396.511719 L 420.476562 392.5 L 422.007812 396.488281 \" style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-286,-369)\"/>\n",
       "<path d=\"M 430.875 380.101562 L 485.296875 380.101562 \" style=\"fill:none;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-286,-369)\"/>\n",
       "<path d=\"M 489.296875 380.101562 L 485.296875 380.101562 M 485.296875 378.601562 L 489.296875 380.101562 L 485.296875 381.601562 \" style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-286,-369)\"/>\n",
       "<path d=\"M 532.351562 409 L 513.632812 391.351562 \" style=\"fill:none;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-286,-369)\"/>\n",
       "<path d=\"M 510.722656 388.605469 L 513.632812 391.351562 M 512.601562 392.441406 L 510.722656 388.605469 L 514.660156 390.257812 \" style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-286,-369)\"/>\n",
       "<path d=\"M 512.199219 380.101562 L 567.273438 380.101562 \" style=\"fill:none;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-286,-369)\"/>\n",
       "<path d=\"M 571.273438 380.101562 L 567.273438 380.101562 M 567.273438 378.601562 L 571.273438 380.101562 L 567.273438 381.601562 \" style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-286,-369)\"/>\n",
       "</g>\n",
       "</svg>"
      ],
      "text/plain": [
       "<IPython.core.display.SVG object>"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from IPython.display import SVG\n",
    "SVG(filename=\"../img/forward.svg\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Backpropagation\n",
    "\n",
    "Backpropagation refers to the method of calculating\n",
    "the gradient of neural network parameters.\n",
    "In general, back propagation calculates and stores\n",
    "the intermediate variables of an objective function\n",
    "related to each layer of the neural network\n",
    "and the gradient of the parameters\n",
    "in the order of the output layer to the input layer\n",
    "according to the ‘chain rule’ in calculus.\n",
    "Assume that we have functions $\\mathsf{Y}=f(\\mathsf{X})$\n",
    "and $\\mathsf{Z}=g(\\mathsf{Y}) = g \\circ f(\\mathsf{X})$,\n",
    "in which the input and the output\n",
    "$\\mathsf{X}, \\mathsf{Y}, \\mathsf{Z}$\n",
    "are tensors of arbitrary shapes.\n",
    "By using the chain rule, we can compute\n",
    "the derivative of $\\mathsf{Z}$ wrt. $\\mathsf{X}$ via\n",
    "\n",
    "$$\\frac{\\partial \\mathsf{Z}}{\\partial \\mathsf{X}} = \\text{prod}\\left(\\frac{\\partial \\mathsf{Z}}{\\partial \\mathsf{Y}}, \\frac{\\partial \\mathsf{Y}}{\\partial \\mathsf{X}}\\right).$$\n",
    "\n",
    "Here we use the $\\text{prod}$ operator\n",
    "to multiply its arguments after the necessary operations,\n",
    "such as transposition and swapping input positions have been carried out.\n",
    "For vectors, this is straightforward:\n",
    "it is simply matrix-matrix multiplication\n",
    "and for higher dimensional tensors we use the appropriate counterpart.\n",
    "The operator $\\text{prod}$ hides all the notation overhead.\n",
    "\n",
    "The parameters of the simple network with one hidden layer\n",
    "are $\\mathbf{W}^{(1)}$ and $\\mathbf{W}^{(2)}$.\n",
    "The objective of backpropagation is to\n",
    "calculate the gradients $\\partial J/\\partial \\mathbf{W}^{(1)}$\n",
    "and $\\partial J/\\partial \\mathbf{W}^{(2)}$.\n",
    "To accomplish this, we will apply the chain rule\n",
    "and calculate, in turn, the gradient of\n",
    "each intermediate variable and parameter.\n",
    "The order of calculations are reversed\n",
    "relative to those performed in forward propagation,\n",
    "since we need to start with the outcome of the compute graph\n",
    "and work our way towards the parameters.\n",
    "The first step is to calculate the gradients\n",
    "of the objective function $J=L+s$\n",
    "with respect to the loss term $L$\n",
    "and the regularization term $s$.\n",
    "\n",
    "$$\\frac{\\partial J}{\\partial L} = 1 \\text{ and } \\frac{\\partial J}{\\partial s} = 1$$\n",
    "\n",
    "Next, we compute the gradient of the objective function\n",
    "with respect to variable of the output layer $\\mathbf{o}$\n",
    "according to the chain rule.\n",
    "\n",
    "$$\n",
    "\\frac{\\partial J}{\\partial \\mathbf{o}}\n",
    "= \\text{prod}\\left(\\frac{\\partial J}{\\partial L}, \\frac{\\partial L}{\\partial \\mathbf{o}}\\right)\n",
    "= \\frac{\\partial L}{\\partial \\mathbf{o}}\n",
    "\\in \\mathbb{R}^q\n",
    "$$\n",
    "\n",
    "Next, we calculate the gradients of the regularization term\n",
    "with respect to both parameters.\n",
    "\n",
    "$$\\frac{\\partial s}{\\partial \\mathbf{W}^{(1)}} = \\lambda \\mathbf{W}^{(1)}\n",
    "\\text{ and }\n",
    "\\frac{\\partial s}{\\partial \\mathbf{W}^{(2)}} = \\lambda \\mathbf{W}^{(2)}$$\n",
    "\n",
    "Now we are able calculate the gradient\n",
    "$\\partial J/\\partial \\mathbf{W}^{(2)} \\in \\mathbb{R}^{q \\times h}$\n",
    "of the model parameters closest to the output layer.\n",
    "Using the chain rule yields:\n",
    "\n",
    "$$\n",
    "\\frac{\\partial J}{\\partial \\mathbf{W}^{(2)}}\n",
    "= \\text{prod}\\left(\\frac{\\partial J}{\\partial \\mathbf{o}}, \\frac{\\partial \\mathbf{o}}{\\partial \\mathbf{W}^{(2)}}\\right) + \\text{prod}\\left(\\frac{\\partial J}{\\partial s}, \\frac{\\partial s}{\\partial \\mathbf{W}^{(2)}}\\right)\n",
    "= \\frac{\\partial J}{\\partial \\mathbf{o}} \\mathbf{h}^\\top + \\lambda \\mathbf{W}^{(2)}\n",
    "$$\n",
    "\n",
    "To obtain the gradient with respect to $\\mathbf{W}^{(1)}$\n",
    "we need to continue backpropagation\n",
    "along the output layer to the hidden layer.\n",
    "The gradient with respect to the hidden layer's outputs\n",
    "$\\partial J/\\partial \\mathbf{h} \\in \\mathbb{R}^h$ is given by\n",
    "\n",
    "\n",
    "$$\n",
    "\\frac{\\partial J}{\\partial \\mathbf{h}}\n",
    "= \\text{prod}\\left(\\frac{\\partial J}{\\partial \\mathbf{o}}, \\frac{\\partial \\mathbf{o}}{\\partial \\mathbf{h}}\\right)\n",
    "= {\\mathbf{W}^{(2)}}^\\top \\frac{\\partial J}{\\partial \\mathbf{o}}.\n",
    "$$\n",
    "\n",
    "Since the activation function $\\phi$ applies element-wise,\n",
    "calculating the gradient $\\partial J/\\partial \\mathbf{z} \\in \\mathbb{R}^h$\n",
    "of the intermediate variable $\\mathbf{z}$\n",
    "requires that we use the element-wise multiplication operator,\n",
    "which we denote by $\\odot$.\n",
    "\n",
    "$$\n",
    "\\frac{\\partial J}{\\partial \\mathbf{z}}\n",
    "= \\text{prod}\\left(\\frac{\\partial J}{\\partial \\mathbf{h}}, \\frac{\\partial \\mathbf{h}}{\\partial \\mathbf{z}}\\right)\n",
    "= \\frac{\\partial J}{\\partial \\mathbf{h}} \\odot \\phi'\\left(\\mathbf{z}\\right).\n",
    "$$\n",
    "\n",
    "Finally, we can obtain the gradient\n",
    "$\\partial J/\\partial \\mathbf{W}^{(1)} \\in \\mathbb{R}^{h \\times d}$\n",
    "of the model parameters closest to the input layer.\n",
    "According to the chain rule, we get\n",
    "\n",
    "$$\n",
    "\\frac{\\partial J}{\\partial \\mathbf{W}^{(1)}}\n",
    "= \\text{prod}\\left(\\frac{\\partial J}{\\partial \\mathbf{z}}, \\frac{\\partial \\mathbf{z}}{\\partial \\mathbf{W}^{(1)}}\\right) + \\text{prod}\\left(\\frac{\\partial J}{\\partial s}, \\frac{\\partial s}{\\partial \\mathbf{W}^{(1)}}\\right)\n",
    "= \\frac{\\partial J}{\\partial \\mathbf{z}} \\mathbf{x}^\\top + \\lambda \\mathbf{W}^{(1)}.\n",
    "$$\n",
    "\n",
    "## Training a Model\n",
    "\n",
    "When training networks, forward and backward propagation depend on each other. In particular, for forward propagation,\n",
    "we traverse the compute graph in the direction of dependencies\n",
    "and compute all the variables on its path.\n",
    "These are then used for backpropagation\n",
    "where the compute order on the graph is reversed.\n",
    "One of the consequences is that we need to retain\n",
    "the intermediate values until backpropagation is complete.\n",
    "This is also one of the reasons why backpropagation\n",
    "requires significantly more memory than plain 'inference'—we end up\n",
    "computing tensors as gradients\n",
    "and need to retain all the intermediate variables\n",
    "to invoke the chain rule.\n",
    "Another reason is that we typically train\n",
    "with minibatches containing more than one variable,\n",
    "thus more intermediate activations need to be stored.\n",
    "\n",
    "## Summary\n",
    "\n",
    "* Forward propagation sequentially calculates and stores intermediate variables within the compute graph defined by the neural network. It proceeds from input to output layer.\n",
    "* Back propagation sequentially calculates and stores the gradients of intermediate variables and parameters within the neural network in the reversed order.\n",
    "* When training deep learning models, forward propagation and back propagation are interdependent.\n",
    "* Training requires significantly more memory and storage.\n",
    "\n",
    "\n",
    "## Exercises\n",
    "\n",
    "1. Assume that the inputs $\\mathbf{x}$ are matrices. What is the dimensionality of the gradients?\n",
    "1. Add a bias to the hidden layer of the model described in this chapter.\n",
    "    * Draw the corresponding compute graph.\n",
    "    * Derive the forward and backward propagation equations.\n",
    "1. Compute the memory footprint for training and inference in model described in the current chapter.\n",
    "1. Assume that you want to compute *second* derivatives. What happens to the compute graph? Is this a good idea?\n",
    "1. Assume that the compute graph is too large for your GPU.\n",
    "    * Can you partition it over more than one GPU?\n",
    "    * What are the advantages and disadvantages over training on a smaller minibatch?\n",
    "\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
